ICPC Live Archive/3928 - Ballroom lights/3928.cpp

   1 // Andrés Mejía
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <numeric>
   7 #include <sstream>
   8 #include <fstream>
   9 #include <cassert>
  10 #include <climits>
  11 #include <cstdlib>
  12 #include <cstring>
  13 #include <string>
  14 #include <cstdio>
  15 #include <vector>
  16 #include <cmath>
  17 #include <queue>
  18 #include <deque>
  19 #include <stack>
  20 #include <list>
  21 #include <map>
  22 #include <set>
  23
  24 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  25 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  26 #define D(x) cout << #x " is " << x << endl
  27
  28 const double EPS = 1e-9;
  29 int cmp(double x, double y = 0, double tol = EPS) {
  30     return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
  31 }
  32
  33 struct point {
  34     long double x, y;
  35     point(){}
  36     point(long double x, long double y) : x(x), y(y) {}
  37 };
  38
  39 typedef pair<point, point> segment;
  40 typedef pair<long double, long double> interval;
  41
  42 struct circle {
  43     point center;
  44     int radius;
  45 };
  46
  47 const int MAXB = 1005;
  48 circle columns[MAXB];
  49 point bulbs[MAXB];
  50
  51 inline long double length(const segment &s) {
  52     long double dx = s.first.x - s.second.x;
  53     long double dy = s.first.y - s.second.y;
  54     return hypotl(dx, dy);
  55 }
  56
  57 pair< bool, long double > segmentIntersection(const segment& s1, const segment& s2) {
  58     point p1 = s1.first;
  59     point p2 = s1.second;
  60     point p3 = s2.first;
  61     point p4 = s2.second;
  62
  63     long double den = (p4.y-p3.y)*(p2.x-p1.x) - (p4.x-p3.x)*(p2.y-p1.y);
  64     long double ua_num = (p4.x-p3.x)*(p1.y-p3.y) - (p4.y-p3.y)*(p1.x-p3.x);
  65     long double ub_num = (p2.x-p1.x)*(p1.y-p3.y) - (p2.y-p1.y)*(p1.x-p3.x);
  66
  67     if (cmp(den, 0) == 0) {
  68         // Caso en que los segmentos son paralelos
  69         if (cmp(ua_num - ub_num, 0) == 0 && cmp(ub_num, 0) == 0) {
  70             // Las rectas son coincidentes, esto no deberia ocurrir
  71             assert(false);
  72         }
  73         return make_pair(false, 0);
  74     }
  75
  76     if (cmp(ub_num/den, 0) >= 0) {
  77         return make_pair(true, ua_num/den);
  78     }
  79     return make_pair(false, 0);
  80 }
  81
  82
  83 interval findShadow(const segment &wall, const point &light, const circle &column) {
  84     long double dx = 1.0L * column.center.x - light.x;
  85     long double dy = 1.0L * column.center.y - light.y;
  86     long double h = sqrt(dx * dx + dy * dy);
  87     long double beta = atan2(dy, dx);
  88     long double alpha = asin(column.radius / h);
  89
  90     //printf("Radius = %d, h = %Lf, r / h = %Lf\n", column.radius, h, column.radius / h);
  91     //printf("beta = %Lf\n", beta);
  92     //printf("alpha = %Lf\n", alpha);
  93
  94     long double d = sqrt(h * h - column.radius * column.radius);
  95     point a(light.x + d * cos(beta + alpha), light.y + d * sin(beta + alpha));
  96     point b(light.x + d * cos(beta - alpha), light.y + d * sin(beta - alpha));
  97
  98     // printf("Must intersect segment that starts at (%Lf, %Lf) and advances up to (%Lf, %Lf)\n", light.x, light.y, light.x + d * cos(beta + alpha), light.y + d * sin(beta + alpha));
  99     // printf("Must intersect segment that starts at (%Lf, %Lf) and advances up to (%Lf, %Lf)\n", light.x, light.y, light.x + d * cos(beta - alpha), light.y + d * sin(beta - alpha));
 100
 101     pair<bool, long double> p1 = segmentIntersection(wall, segment(light, a) );
 102     pair<bool, long double> p2 = segmentIntersection(wall, segment(light, b) );
 103
 104     interval shadow;
 105     long double length = hypotl(wall.first.x - wall.second.x, wall.first.y - wall.second.y);
 106
 107     if (!p1.first) {
 108         if (!p2.first) {
 109             // Everything's lit, no shadow.
 110             return interval(0, 0);
 111         } else {
 112             shadow = interval(0, p2.second);
 113         }
 114     } else {
 115         if (!p2.first) {
 116             shadow = interval(p1.second, 1);
 117         } else {
 118             shadow = interval(p1.second, p2.second);
 119         }
 120     }
 121     shadow.first = max(0.0L, min(1.0L, shadow.first) );
 122     shadow.second = max(0.0L, min(1.0L, shadow.second) );
 123
 124     shadow.first *= length;
 125     shadow.second *= length;
 126     //printf("Shadow: [%Lf, %Lf]\n", shadow.first, shadow.second);
 127     return shadow;
 128 }
 129
 130 vector< interval > merge(vector<interval> &v) {
 131     sort(v.begin(), v.end());
 132     vector< interval > ans;
 133     if (v.size() <= 1) return v;
 134     long double left = v[0].first, right = v[0].second;
 135     for (int i = 0; i < v.size(); ++i) {
 136         if (i + 1 < v.size() and cmp(left, v[i+1].first) <= 0 and cmp(v[i+1].first, right) <= 0 ) {
 137             right = max(right, v[i+1].second);
 138         } else {
 139             if (cmp(right - left, 0) > 0) {
 140                 ans.push_back( interval(left, right) );
 141             }
 142             if (i + 1 < v.size()) {
 143                 left = v[i + 1].first;
 144                 right = v[i + 1].second;
 145             }
 146         }
 147     }
 148     return ans;
 149 }
 150
 151 vector< interval > invert(const vector<interval> v, long double length) {
 152     if (v.size() == 0) {
 153         return vector<interval>(1, interval(0, length) ); // Everything
 154     }
 155
 156     vector< interval > ans;
 157     // Before the beginning
 158     if (cmp(0, v[0].first) < 0) {
 159         ans.push_back(interval(0, v[0].first));
 160     }
 161
 162     // between
 163     for (int i = 0; i < v.size() - 1; ++i) {
 164         ans.push_back(interval(v[i].second, v[i + 1].first) );
 165     }
 166
 167     // After the end
 168     if (cmp(v.back().second, length) < 0) {
 169         ans.push_back(interval(v.back().second, length));
 170     }
 171     return ans;
 172 }
 173
 174 int main(){
 175     int L, C, X, Y;
 176     while (scanf("%d %d %d %d", &L, &C, &X, &Y) == 4) {
 177         if (L == 0 and C == 0 and X == 0 and Y == 0) break;
 178         for (int i = 0; i < L; ++i) {
 179             int x, y;
 180             scanf("%d %d", &x, &y);
 181             bulbs[i].x = x;
 182             bulbs[i].y = y;
 183         }
 184         for (int i = 0; i < C; ++i){
 185             int x, y, r;
 186             scanf("%d %d %d", &x, &y, &r);
 187             columns[i].center.x = x;
 188             columns[i].center.y = y;
 189             columns[i].radius = r;
 190         }
 191
 192         vector< segment > walls;
 193         walls.push_back(  segment(point(0, 0), point(0, Y))   );
 194         walls.push_back(  segment(point(0, Y), point(X, Y))   );
 195         walls.push_back(  segment(point(X, Y), point(X, 0))   );
 196         walls.push_back(  segment(point(X, 0), point(0, 0))   );
 197
 198         long double ans = 0;
 199         for (int i = 0; i < walls.size(); ++i) {
 200             vector< interval > allLights; // lights on this wall caused by all different lightbulbs
 201             for (int j = 0; j < L; ++j) {
 202                 vector< interval > shadows; // shadows on this wall caused only by this light
 203                 for (int k = 0; k < C; ++k) {
 204                     shadows.push_back( findShadow(walls[i], bulbs[j], columns[k]) );
 205                 }
 206
 207                 // printf("Shadows on wall (%.0Lf, %.0Lf) to (%.0Lf, %.0Lf) caused by light at (%.0Lf, %.0Lf):\n",
 208                 //     walls[i].first.x, walls[i].first.y, walls[i].second.x, walls[i].second.y, bulbs[j].x, bulbs[j].y);
 209                 // printf("Before merging:\n");
 210                 // for (int k = 0; k < shadows.size(); ++k) { printf("[%Lf, %Lf] ", shadows[k].first, shadows[k].second); } puts("");
 211
 212                 shadows = merge(shadows); // Merge overlapping shadows
 213
 214                 // printf("After merging:\n");
 215                 // for (int k = 0; k < shadows.size(); ++k) { printf("[%Lf, %Lf] ", shadows[k].first, shadows[k].second); } puts("");
 216
 217                 // Everything that's not a shadow caused by this light, is certainly lit.
 218                 vector<interval> lights = invert(shadows, length(walls[i]) );
 219
 220                 // printf("Sections I know to be lit on wall (%.0Lf, %.0Lf) to (%.0Lf, %.0Lf) caused by light at (%.0Lf, %.0Lf):\n",
 221                 //                                          walls[i].first.x, walls[i].first.y, walls[i].second.x, walls[i].second.y, bulbs[j].x, bulbs[j].y);
 222                 //                                 for (int k = 0; k < lights.size(); ++k) { printf("[%Lf, %Lf] ", lights[k].first, lights[k].second); } puts("");
 223                 allLights.insert(allLights.end(), lights.begin(), lights.end());
 224             }
 225             allLights = merge(allLights); // Merge overlapping lit zones
 226             for (int i = 0; i < allLights.size(); ++i) {
 227                 //printf("Lit: [%Lf, %Lf]\n", allLights[i].first, allLights[i].second);
 228                 ans += allLights[i].second - allLights[i].first;
 229             }
 230         }
 231         printf("%.4Lf\n", ans);
 232
 233     }
 234     return 0;
 235 }